Most of the time, confidentiality is not enough - it needs to be combined with integrity in order for an application to be secure. So, even if an encryption scheme is CCA-secure, there is still room for ciphertext forgery. This necessitates even stronger security notions which are satisfied by authenticated encryption schemes.
A cipher $(\textit{Enc}, \textit{Dec})$ is an *authenticated encryption* scheme or is *AE-secure* if it is [CPA-secure](Security%20Notions/Chosen%20Plaintext%20Attack%20(CPA).md) and provides [ciphertext integrity (CI)](Security%20Notions/Ciphertext%20Integrity%20(CI).md).
AE-security is the most widely adopted security notion and is ubiquitous in web applications. It is stronger than CCA-security - the constructs which satisfy AE-security also satisfy CCA-security. However, there is no real efficiency difference between ciphers which are AE-secure and ciphers which are only CCA-secure.
Every AE-secure cipher is also CCA-secure.
Let $(\textit{Enc}, \textit{Dec})$ be an AE-secure cipher and let $\textit{Mallory}$ be a CCA-adversary. In particular, suppose that Mallory makes $q_e$ encryption queries to obtain the plaintext-ciphertext pairs $(m_1,c_1), (m_2,c_2), ..., (m_{q_e},c_{q_e})$ and also makes $q_d$ decryption queries to obtain the ciphertext-plaintext pairs $(c_1', m_1'), (c_2', m_2'), ..., (c_{q_d}', m_{q_d}')$.
Since the cipher is AE-secure and thus provides ciphertext integrity, the probability that in a given decryption query Mallory finds a ciphertext $c_j'$ such that $\textit{Dec}_k(c_j') \ne \textbf{error}$ is negligible. Mallory sumbits $q_d$ queries, so the probability that any of them turn out to be valid is $q_d\cdot\textit{negl}(n)$, which is also negligible. This means that the decryption queries do not help Mallory in any way and can be ignored, thereby reducing the CCA scenario to a CPA one. AE-security provides CPA-security by definition, which completes the proof.
This explains why ciphers which are only CCA-secure are rarely used in practice - why would you opt for less security when there is not even an efficiency benefit?
There are many ways to implement authenticated encryption. Some include combining a CPA-secure cipher with a secure
AE-secure encryption schemes can be constructed by combining a CPA-secure cipher
However, it turns out that not all ways of combining these two systems yield an authenticated encryption and even if the correct approach is used, the keys
In this approach, encryption and message signing are carried out independently from each other and in parallel. The supposedly AE-secure cipher
The final ciphertext is the concatenation of
To decrypt the ciphertext
This is certainly a good attempt at constructing an authenticated encryption but it fails horribly.
The Encrypt-and-Sign approach is *not* AE-secure.
Since the message
Moreover, it is not CPA-secure because deterministic MACs will produce the same tag when given the same message, provided that the same signing key
In this approach the first step is to compute the tag
The decryption function decrypts the ciphertext
The Sign-then-Encrypt approach *may* be AE-secure, but this depends highly on the specifics of the cipher and the MAC used. Since it does not provide AE-security in the general case of an arbitrary cipher and an arbitrary MAC, it should be avoided - there is simply too much room for mistakes when implementing it.
For example, if there are different error types depending on whether validation or decryption fails, something which is very much necessary in practice, then the security of this approach can be broken by padding oracle attacks.
This approach requires a MAC system with strong unforgeablity. First, the message is encrypted. The resulting ciphertext
The decryption function parses the ciphertext
This approach is quite similar to Encrypt-and-Sign, but the tag is computed on the ciphertext instead of the plaintext. This small difference turns out to be crucial as it is what makes Encrypt-then-Sign AE-secure. Since the tag is verifying the ciphertext, no adversary can tamper with it. This reduces any CCA adversary to a CPA adversary and the CPA-security of
Suppose that $\mathcal{A}$ is a CCA adversary.
For each of the adversary's decryption queries, the strong unforgeability of the MAC guarantees that the probability that $\mathcal{A}$ can produce a valid ciphertext $c||\tau$ is negligible, since to produce such a ciphertext, $\mathcal{A}$ would have to find a valid ciphertext-tag pair. The MAC system is secure, so this only happens with probability at most $\frac{1}{2^n} + \textit{negl(n)}$, which is negligible. If $\mathcal{A}$ makes $q$ decryption queries, then the probability that one of them is valid is $q(\frac{1}{2^n} + \textit{negl}(n))$ which is also negligible, since $q$ has to be polynomial. This means that the cipher provides [ciphertext integrity (CI)](../Security%20Notions/Ciphertext%20Integrity%20(CI).md), even in the more empowering scenario which allows $\mathcal{A}$ to submit decryption queries.
What remains is to prove that the cipher $(\textit{Enc}, \textit{Dec}')$ is CPA-secure (remember that CPA-security combined with the already established ciphertext integrity implies CCA-security). Suppose, towards contradiction, that $\mathcal{B}$ is a CPA adversary which can break the CPA-security of $(\textit{Enc}, \textit{Dec})$, i.e. $\mathcal{B}$ can distinguish if a ciphertext $c||\tau$ is the encryption of $m_a$ or $m_b$ with probability $\frac{1}{2} + \textit{nonnegl}(n)$.
Now, let $\mathcal{B}'$ be a CPA adversary against $(\textit{Enc}',\textit{Dec}')$. When $\mathcal{B}'$ receives its challenge ciphertext $c$, it will compute its tag $\tau$ (this is allowed because the signing key $k_S$ is different from the encryption key $k_E$) and then it will forward $c||\tau$ together with $m_a$ and $m_b$ to $\mathcal{B}$. However, the adversary $\mathcal{B}$ is also a CPA adversary (albeit against $(\textit{Enc}, \textit{Dec})$) and may thus require encryption queries to achieve its goal. This is no problem as $\mathcal{B}'$ can provide answers to any encryption queries that $\mathcal{B}$ might have. Whenever $\mathcal{B}$ submits a plaintext $m$ as a query, the adversary $\mathcal{B}'$ will be able to fulfil it by using its own encryption oracle $\textit{Enc}'$ and then computing the tag for the resulting ciphertext.
Ultimately, $\mathcal{B}'$ will output whichever message, either $m_a$ or $m_b$, that $\mathcal{B}$ does. Since $\mathcal{B}$ will guess correctly if $c||\tau$ is the encryption of $m_a$ or $m_b$ with probability $\frac{1}{2} + \textit{nonnegl}(n)$, then $\mathcal{B}'$ will guess if $c$ is the encryption of $m_a$ or $m_b$ with probability $\frac{1}{2} + \textit{nonnegl}(n)$. This is a contradiction, since it would be a breach of the CPA-security of $(\textit{Enc}',\textit{Dec}')$.
It is paramount that the MAC system used has strong unforgeability. Otherwise, a CCA adversary challenged with a ciphertext